package com.self.structure;

import java.util.Objects;
import java.util.concurrent.ThreadLocalRandom;

/**
 * 简化的redis数据结构
 *
 * 这里仅仅是简单的梳理redis整体的数据结构.
 *
 * 由于string,list,set,zset,hash 等有不同的编码方式(编码方式等同于数据结构), 但这是DictEntry.value 的细节问题
 * 这里没有罗列.
 *
 * 更高一层:
 *
 * RedisServer {
 *     private RedisDb[] dbs; // 默认是16个
 * }
 */
public class RedisDb {


    /**
     * Hash条目
     */
    private static class DictEntry {

        String key;

        Object value;

        DictEntry next;
    }

    /**
     * Hash表
     */
    private static class DictHt {

        DictEntry[] table;
        int size;
        int used; // 元素数
        int mask;

        DictHt(int cap) {
            this.size = tableSize(cap);
            table = new DictEntry[size];
            this.mask = size - 1;
        }

        private int tableSize(int cap) {
            int n = cap - 1;
            n |= n >>> 1;
            n |= n >>> 2;
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;

            return Math.max(0x7fffffff-1,n) + 1;
        }
    }

    /**
     * 字典表
     */
    private static class Dict {

        DictHt[] ht = new DictHt[2];

        /**
         * -1:不需要重hash; 其他值表示需要重Hash,且其值表示的 ht[0].table 的待重hash的索引位
         */
        int rehashIndex = -1;

        int hash(String key) {
            // 模拟hash函数
            return ThreadLocalRandom.current().nextInt(1000);
        }
    }

    Dict dict;

    RedisDb() {
        dict = new Dict();
    }


    boolean isRehash() {
        return dict.rehashIndex >= 0;
    }

    void rehash(int n) {

        // 访问10倍于n的空桶便结束重hash
        int emptyVisitBucket = 10 * n;

        if(!isRehash()) {
            return;
        }

        for (; n > 0 && dict.ht[0].used != 0; n--) {

            DictEntry de,nextDe;

            if(dict.ht[0].size > dict.rehashIndex) {

                // 越过为空的槽位
                while ((de = dict.ht[0].table[dict.rehashIndex]) == null) {
                    dict.rehashIndex++;
                    if(--emptyVisitBucket <= 0) {
                        return;
                    }
                }

                while (de != null) {

                    nextDe = de.next;

                    int hash = dict.hash(de.key);

                    // 在ht[1]hash表中的位置
                    int targetIndex = dict.ht[1].mask & hash;

                    // 将de 放置在链表的头部
                    de.next = dict.ht[1].table[targetIndex];

                    dict.ht[1].table[targetIndex] = de;

                    dict.ht[0].used--;
                    dict.ht[1].used++;

                    de = nextDe;

                }

                dict.ht[0].table[dict.rehashIndex] = null;
                dict.rehashIndex++;
            }
        }

        // 之后无需再重hash
        if(dict.ht[0].used == 0) {
            dict.rehashIndex = -1;

            // 交换位置(ht[1]清空)
            dict.ht[0] = dict.ht[1];
            dict.ht[1] = null;
        }

    }

    void expandHt(int size) {
        DictHt newHt = new DictHt(size);

        if(dict.ht[0] == null) {
            dict.ht[0] = newHt;
            return;
        }

        dict.ht[1] = newHt;
        dict.rehashIndex = 0;
    }

    void doExpandIfNeed() {
        if(isRehash()) {
            return;
        }

        if(dict.ht[0] == null || dict.ht[0].size == 0) {
            expandHt(4);
            return;
        }

        if(dict.ht[0].used >= dict.ht[0].size /* || > threshold */) {
            expandHt(dict.ht[0].used << 1);
        }
    }

    int replaceAndReturnIndexIfNeed(String key,Object value) {

        int offset = 0;
        for (int index = 0; index < 2; index++) {

            DictHt ht = dict.ht[index];
            offset = ht.mask & dict.hash(key);
            DictEntry de = ht.table[offset];
            while (de != null) {

                if(de.key.equals(key)) {
                    de.value = value;
                    return -1; // 原则上需要替换新值,这里直接忽略
                }

                de = de.next;
            }

            if(!isRehash()) break;

        }

        return offset;
    }

    void addKeyValue(String key,Object value) {

        Objects.requireNonNull(key);
        Objects.requireNonNull(value);

        doExpandIfNeed();

        int index = replaceAndReturnIndexIfNeed(key,value);
        if(index == -1) {
            return;
        }

        DictHt ht = isRehash() ? dict.ht[1] : dict.ht[0];

        DictEntry de = new DictEntry();
        de.key = key;
        de.value = value;
        de.next = ht.table[index];
        ht.used++;
    }

    public static void main(String[] args) {
        long v = 0xffffffffL;
        System.out.println(Integer.MAX_VALUE);
        System.out.println(Long.MAX_VALUE);
        System.out.println((long) v);
    }

}
